package com.mytest.offer;

import lombok.extern.slf4j.Slf4j;

import java.util.Stack;

@Slf4j
public class Solution31 {

    public static void main(String[] args) {
        int [] pushed = {2, 3, 5, 4, 6, 7};

        int [] popped = {4, 5, 6, 7, 3, 2};
        Solution31 solution31 = new Solution31();
        boolean b = solution31.validateStackSequences(pushed, popped);
        log.info("{}", b);
    }

    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Stack<Integer> stack = new Stack();
        int i = 0;
        for (int num : pushed) {
            stack.push(num);
            while(!stack.empty() && stack.peek() == popped[i]) {
                stack.pop();
                i++;
            }
        }
        return stack.empty();
    }

    public boolean validateStackSequences1(int[] pushed, int[] popped) {
        if (pushed.length == 0 && popped.length == 0) {
            return true;
        }
        if (pushed.length != popped.length) {
            return false;
        }
        int middle = popped[0];
        int targetIndex = 0;
        for (int j = 0; j < pushed.length ; j++){
            if(pushed[j] == middle){
                targetIndex = j;
                break;
            }
        }
        int left = targetIndex, right = targetIndex;
        for(int i = 1; i < popped.length; i++){

            if (left > 0 && popped[i] == pushed[left-1]){
                left = left -1;
            }
            if (right < popped.length - 1 && popped[i] == pushed[right+1]){
                right = right + 1;
            }
        }
        if(left == 0  && right == pushed.length - 1){
            return true;
        }
        return false;
    }
}
